#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#ifndef FALLOC_H
# error must include falloc
#endif
#ifndef CORE_H
# include "Core.h"
#endif

namespace System {

	template <typename T>
	class LinkedList;

	template <typename T>
	class LinkedListNode
	{
	friend class LinkedList<T>;
	private:
		LinkedList<T>* _list;
        LinkedListNode<T>* _next;
        LinkedListNode<T>* _prev;

	public:
		T Value;

		__device__ void xtor(T value)
		{
			_list = nullptr;
			Value = value;
		}
		__device__ void xtor(LinkedList<T>* list, T value)
		{
			_list = list;
			Value = value;
		}

        __forceinline __device__ void Invalidate()
        {
            _list = nullptr;
            _next = nullptr;
            _prev = nullptr;
        }

        __forceinline __device__ LinkedList<T>* getList() { trace(LinkedListNode, "getList"); return _list; }
        __forceinline __device__ LinkedListNode<T>* getNext() { return (_next != nullptr && _next != _list->_head ? _next : nullptr); }
		__forceinline __device__ LinkedListNode<T>* getPrevious() { return (_prev != nullptr && _prev != _list->_head ? _prev : nullptr); }
	};

	template <typename T>
	class LinkedList
	{ 
	friend class LinkedListNode<T>;
	private:
		fallocContext* _fallocCtx;
        LinkedListNode<T>* _head;
        int _count;
        int _version;

		 __device__ void InternalInsertNodeBefore(LinkedListNode<T>* node, LinkedListNode<T>* newNode)
        {
            newNode->_next = node;
            newNode->_prev = node->_prev;
            node->_prev->_next = newNode;
            node->_prev = newNode;
            _version++;
            _count++;
        }

        __device__ void InternalInsertNodeToEmptyList(LinkedListNode<T>* newNode)
        {
            newNode->_next = newNode;
            newNode->_prev = newNode;
            _head = newNode;
            _version++;
            _count++;
        }

        __device__ void InternalRemoveNode(LinkedListNode<T>* node)
        {
            if (node->_next == node)
                _head = nullptr;
            else
            {
                node->_next->_prev = node->_prev;
                node->_prev->_next = node->_next;
                if (_head == node)
                    _head = node->_next;
            }
            node->Invalidate();
            _count--;
            _version++;
        }

		 __device__ void ValidateNewNode(LinkedListNode<T>* node)
        {
            if (node == nullptr)
                thrownew(ArgumentNullException, "node");
            if (node->_list != nullptr)
                thrownew(InvalidOperationException, "LinkedListNodeIsAttached");
        }

        __device__ void ValidateNode(LinkedListNode<T>* node)
        {
            if (node == nullptr)
                thrownew(ArgumentNullException, "node");
            if (node->_list != this)
                thrownew(InvalidOperationException, "ExternalLinkedListNode");
        }

	public:
		__device__ void xtor(fallocContext* fallocCtx)
		{
			_fallocCtx = fallocCtx;
			_head = nullptr;
			_version = 0;
			_count = 0;
		}

		__device__ LinkedListNode<T>* AddAfter(LinkedListNode<T>* node, T value)
        {
            ValidateNode(node);
            LinkedListNode<T>* newNode = falloc<LinkedListNode<T>>(_fallocCtx); newNode->xtor(node->_list, value);
            InternalInsertNodeBefore(node->_next, newNode);
            return newNode;
        }

		__device__ void AddAfter(LinkedListNode<T>* node, LinkedListNode<T>* newNode)
        {
            ValidateNode(node);
			ValidateNewNode(newNode);
            InternalInsertNodeBefore(node->_next, newNode);
            newNode->_list = this;
        }

		__device__ void AddBefore(LinkedListNode<T>* node, LinkedListNode<T>* newNode)
        {
            ValidateNode(node);
            ValidateNewNode(newNode);
            InternalInsertNodeBefore(node, newNode);
            newNode->_list = this;
            if (node == _head)
                _head = newNode;
        }

        __device__ LinkedListNode<T>* AddBefore(LinkedListNode<T>* node, T value)
        {
            ValidateNode(node);
            LinkedListNode<T>* newNode = falloc<LinkedListNode<T>>(_fallocCtx); newNode->xtor(node->_list, value);
            InternalInsertNodeBefore(node, newNode);
            newNode->_list = this;
            if (node == _head)
                _head = newNode;
			return newNode;
        }

	    __device__ void AddFirst(LinkedListNode<T>* node)
        {
            ValidateNewNode(node);
            if (_head == nullptr)
                InternalInsertNodeToEmptyList(node);
            else
            {
                InternalInsertNodeBefore(_head, node);
                _head = node;
            }
            node->_list = this;
        }

        __device__ LinkedListNode<T>* AddFirst(T value)
        {
            LinkedListNode<T>* newNode = falloc<LinkedListNode<T>>(_fallocCtx); newNode->xtor(this, value);
            if (_head == nullptr)
			{
                InternalInsertNodeToEmptyList(newNode);
				return newNode;
			}
            InternalInsertNodeBefore(_head, newNode);
            _head = newNode;
			return newNode;
        }

        __device__ LinkedListNode<T>* AddLast(T value)
        {
            LinkedListNode<T>* newNode = falloc<LinkedListNode<T>>(_fallocCtx); newNode->xtor(this, value);
            if (_head == nullptr)
			{
                InternalInsertNodeToEmptyList(newNode);
				return newNode;
			}
            InternalInsertNodeBefore(_head, newNode);
            return newNode;
        }

		__device__ void AddLast(LinkedListNode<T>* node)
        {
            ValidateNewNode(node);
            if (_head == nullptr)
                InternalInsertNodeToEmptyList(node);
            else
                InternalInsertNodeBefore(_head, node);
            node->_list = this;
        }

        __device__ void Clear()
        {
            LinkedListNode<T>* head = _head;
            while (head != nullptr)
            {
                LinkedListNode<T>* node2 = head;
                head = head->getNext();
                node2->Invalidate();
            }
            _head = nullptr;
            _count = 0;
            _version++;
        }

        __device__ void Remove(LinkedListNode<T>* node)
        {
            ValidateNode(node);
            InternalRemoveNode(node);
        }

        __device__ void RemoveFirst()
        {
            if (_head == nullptr)
                thrownew(InvalidOperationException, "LinkedListEmpty");
            InternalRemoveNode(_head);
        }

        __device__ void RemoveLast()
        {
            if (_head == nullptr)
                thrownew(InvalidOperationException, "LinkedListEmpty");
            InternalRemoveNode(_head->_prev);
        }

        __device__ int getCount()  { return _count; }
        __device__ LinkedListNode<T>* getFirst()  { return _head; }
        __device__ LinkedListNode<T>* getLast()  {  return (_head != nullptr ? _head->_prev : nullptr); }

		#pragma region Enumerator

		//////////////////////////
		// ENUMERATOR
        typedef struct Enumerator_t
        {
		private:
            //LinkedList<T>* _list;
            LinkedListNode<T>* _node;
            int _version;
            int _index;

		public:
			T Current;

			__device__ void xtor(LinkedList<T>* list)
			{
				//_list = list;
				_version = list->_version;
				_node = list->_head;
				Current = 0;
				_index = 0;
			}
			__device__ void Dispose() { }

			__device__ bool MoveNext(LinkedList<T>* list)
			{
				if (_version != list->_version)
					thrownew(InvalidOperationException, "InvalidOperation_EnumFailedVersion");
				if (_node == nullptr)
				{
					_index = list->getCount() + 1;
					return false;
				}
				_index++;
				Current = _node->Value;
				_node = _node->_next;
				if (_node == list->_head)
					_node = nullptr;
				return true;
			}

			__device__ void Reset(LinkedList<T>* list)
			{
				if (_version != list->_version)
					thrownew(InvalidOperationException, "InvalidOperation_EnumFailedVersion");
				Current = 0;
				_node = list->_head;
				_index = 0;
			}
		} Enumerator;

		__device__ void GetEnumerator(Enumerator& t)
        {
			trace(LinkedList_Enumerator, "GetEnumerator");
			t.xtor(this);
        }

		#pragma endregion
	};

}

#endif // LINKEDLIST_H